﻿#pragma once
#include<vector>
using namespace std;
namespace Ehundred
{
	//线性探测哈希闭散列
	template<class K,class V>
	class HashTable
	{
		enum state
		{
			EMPTY,
			EXIST,
			DELETE
		};

		struct elem
		{
			K _key;
			V _val;
			state _st;
		};
	public:
		HashTable(size_t capacity=10)
			:_size(0)
		{
			_table.resize(capacity);
		}

		bool insert(const K& key, const V& val)
		{
			CheckFactor();

			size_t HashAddress = key % _table.capacity();
			while (_table[HashAddress]._st == EXIST)
			{
				if (_table[HashAddress]._key == key)
					return false;

				HashAddress++;
				
				if (HashAddress == _table.capacity())
					HashAddress = 0;
			}

			_table[HashAddress]._key = key;
			_table[HashAddress]._val = val;
			_table[HashAddress]._st = EXIST;
			_size++;

			return true;
		}

		int find(const K& key)
		{
			size_t HashAddress = key % _table.capacity();

			while (!(_table[HashAddress]._st == EMPTY))
			{
				if (_table[HashAddress]._st == EXIST && _table[HashAddress]._key == key)
					return HashAddress;

				HashAddress++;

				if (HashAddress == _table.capacity())
					HashAddress = 0;
			}

			return -1;
		}

		bool erase(const K& key)
		{
			int HashAddress = find(key);
			if (key == -1)
				return false;

			_table[HashAddress]._st = DELETE;
			_size--;

			return true;
		}

		size_t size() const
		{
			return _size;
		}

		bool empty() const
		{
			return _size == 0;
		}
	private:
		vector<elem> _table;
		size_t _size;
		float MaxLoadFactor = 0.75;

		bool CheckFactor()
		{
			if ((float)_size / _table.capacity() >= MaxLoadFactor)
			{
				HashTable<K, V> newtable(_table.capacity() * 2);
				for (auto e : _table)
				{
					if (e._st == EXIST)
					{
						newtable.insert(e._key,e._val);
					}
				}

				swap(_table, newtable._table);
			}

			return true;
		}
	};

	//哈希桶开散列
	template<class K,class V>
	class HashBucket
	{
		struct ListNode
		{
			K _key;
			V _val;
			ListNode* next=nullptr;
		};	
	public:
		HashBucket(size_t capacity = 10)
			:_size(0)
		{
			_bucket.resize(capacity);
		}

		~HashBucket()
		{
			for (auto e : _bucket)
			{
				ListNode* cur = e;
				while (cur)
				{
					ListNode* next = cur->next;
					delete cur;
					cur = next;
				}
			}
		}

		bool insert(const K& key, const V& val)
		{
			if (find(key))
				return false;

			CheckFactor();

			size_t HashAddress = key % _bucket.capacity();
			ListNode* NewNode = new ListNode;
			NewNode->_key = key;
			NewNode->_val = val;
			NewNode->next = _bucket[HashAddress];
			_bucket[HashAddress] = NewNode;
			_size++;

			return true;
		}

		ListNode* find(const K& key)
		{
			size_t HashAddress = key % _bucket.capacity();

			ListNode* cur = _bucket[HashAddress];
			while (cur)
			{
				ListNode* next = cur->next;
				if (cur->_key == key)
					return cur;

				cur = next;
			}

			return nullptr;
		}

		bool erase(const K& key)
		{
			size_t HashAddress = key % _bucket.capacity();

			ListNode* pre = nullptr;
			ListNode* cur = _bucket[HashAddress];

			while (cur)
			{
				if (cur->_key == key)
				{
					if (pre == nullptr)
					{
						_bucket[HashAddress] = cur->next;
					}
					else
					{
						pre->next = cur->next;
					}

					delete cur;
					return true;
				}

				pre = cur;
				cur = cur->next;
			}

			return false;
		}
	private:
		vector<ListNode*> _bucket;
		size_t _size;
		float MaxLoadFactor = 1;

		void CheckFactor()
		{
			if ((float)_size / _bucket.capacity() >= MaxLoadFactor)
			{
				HashBucket<K, V> newbucket(_bucket.capacity() * 2);
				
				for (auto& e : _bucket)
				{
					ListNode* cur = e;
					while (cur)
					{
						ListNode* next = cur->next;

						size_t HashAddress = cur->_key % newbucket._bucket.capacity();
						
						//把每一个元素头插到新表的对应位置
						cur->next = newbucket._bucket[HashAddress];
						newbucket._bucket[HashAddress] = cur;

						cur = next;
					}

					e = nullptr;
				}

				_bucket.swap(newbucket._bucket);
			}
		}
	};
}